| Algorytm | Czas preprocessingu | Czas dopasowywania | ||
|---|---|---|---|---|
| naiwny | 0 | $O((n-m+1)m)$ | ||
| Rabin-Karp | $\Theta(m)$ | $O((n-m+1)m$ | ||
| automat skończony | $O(m | \Sigma | )$ | $\Theta(n)$ |
| Knuth-Morris-Pratt | $\Theta(m)$ | $\Theta(n)$ |
$x, y, z$ - łańcuchy znaków
$x \sqsupset z \land y \sqsupset z \rightarrow$
def naive_string_matching(text, pattern):
for s in range(0, len(text) - len(pattern) + 1):
if(pattern == text[s:s+len(pattern)]):
print(f"Przesunięcie {s} jest poprawne")
naive_string_matching("abaabaaaaba", "aba")
Przesunięcie 0 jest poprawne Przesunięcie 3 jest poprawne Przesunięcie 8 jest poprawne
Złożoność czasowa dopasowania $O((n - m + 1)m)$
Automat skończony $M$ to krotka $(Q, q_0, A, \Sigma, \delta)$:
$|P| = m$
$\sigma: \Sigma^* \rightarrow \{0, 1, ...m\}$
Jak skonstruować funkcję $\delta$? Kluczowa obserwacja:
$\pmb{\sigma(T_ia) = \sigma(P_qa)}$, gdzie $q = \sigma(T_i)$
Innymi słowy - można to zrobić analizująca sam wzorzec $P$.
def fa_string_matching(text, delta):
q = 0
for s in range(0, len(text)):
q = delta[q][text[s]]
if(q == len(delta) - 1):
print(f"Przesunięcie {s + 1 - q} jest poprawne")
# s + 1 - ponieważ przeczytaliśmy znak o indeksie s, więc przesunięcie jest po tym znaku
Złożoność czasowa dopasowania $\Theta(n)$
pattern = "aba"
delta = [
{"a": 1, "b": 0}, # 0
{"a": 1, "b": 2}, # 1
{"a": 3, "b": 0}, # 2
{"a": 1, "b": 2}, # 3
]
fa_string_matching("abaabaaaaba", delta)
Przesunięcie 0 jest poprawne Przesunięcie 3 jest poprawne Przesunięcie 8 jest poprawne
Przyjmując:
$\pmb{\forall x, a: \sigma(xa) \leq \sigma(x) + 1}$
Niech $r = \sigma(xa)$
Jeśli $r = 0$, wtedy warunek nierówności jest spełniony, ponieważ ponieważ $\sigma$ jest nieujemna.
Przyjmując:
$\pmb{\forall x, a: q = \sigma(x) \rightarrow \sigma(xa) = \sigma(P_qa)}$
Niech:
wtedy
$\pmb{\phi(T_i) = \sigma(T_i)}$
Dowód indukcyjny.
dla $i = 0$, twierdzenie jest prawdziwe, ponieważ $T_0 = \epsilon$, więc $\phi(T_0) = 0 = \sigma(T_0)$,
Załóżmy, że $\phi(T_i) = \sigma(T_i)$ i sprawdźmy, czy $\phi(T_{i+1}) = \sigma(T_{i+1})$.
Niech $q \equiv \phi(T_i)$ oraz $a \equiv T[i+1]$.
$\begin{array}{ccll} \phi(T_{i+1}) & = & \phi(T_ia) & \textrm{z definicji $T_{i+1}$ oraz $a$}\\ & = & \delta(\phi(T_i),a) & \textrm{z definicji $\phi$}\\ & = & \delta(q,a) & \textrm{z defnicji $q$}\\ & = & \sigma(P_qa) & \textrm{z definicji $\delta$}\\ & = & \sigma(T_ia) & \textrm{z lematu 1.3 oraz indukcji}\\ & = & \sigma(T_{i+1}) & \textrm{z definicji $T_{i+1}$} \end{array} $
import re
def transition_table(pattern):
result = []
for q in range(0, len(pattern) + 1):
result.append({})
for a in ["a", "b"]:
k = min(len(pattern) + 1, q + 2)
while True:
k = k - 1
if(re.search(f"{pattern[:k]}$", pattern[:q] + a)):
break
result[q][a] = k
return result
transition_table("aba")
$O(m^3|\Sigma|)$
def kmp_string_matching(text, pattern):
pi = prefix_function(pattern)
q = 0
for i in range(0, len(text)):
while(q > 0 and pattern[q] != text[i]):
q = pi[q-1]
if(pattern[q] == text[i]):
q = q + 1
if(q == len(pattern)):
print(f"Przesunięcie {i + 1 - q} jest poprawne")
q = pi[q-1]
def prefix_function(pattern):
pi = [0]
k = 0
for q in range(1, len(pattern)):
while(k > 0 and pattern[k] != pattern[q]):
k = pi[k-1]
if(pattern[k] == pattern[q]):
k = k + 1
pi.append(k)
return pi
prefix_function("ababaca")
kmp_string_matching("abaabaaaaba", "aba")